Solution: Combination Sum
Let's solve the Combination Sum problem using the Dynamic Programming pattern.
Statement#
Given an array of distinct integers, nums, and an integer, target, return a list of all unique combinations of nums where the chosen numbers sum up to the target. The combinations may be returned in any order.
An integer from nums may be chosen an unlimited number of times. Two combinations are unique if the
frequency of at least one of the chosen integers is different.
Constraints:
-
nums.length -
nums[i] -
target - All integers of
numsare unique.
Solution#
So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.
Naive approach#
A naive approach to solve this problem would be to make all the possible combinations of nums or generate all subsets of nums that sum up to the required target.
This solution is very costly because the time complexity of achieving this is , where is the number of elements in nums, is the target, and is the minimum value in nums. This is because each node in the recursion tree can have branches, and the height of the tree can grow up to . Therefore, the total number of nodes in such a tree is bounded by .
Optimized solution using dynamic programming#
Because the recursive solution to this problem is very costly, let’s see if we can reduce this cost in any way. Dynamic programming helps us avoid recomputing the same subproblems. Now let’s analyze our recursive solution to see if it has the properties needed for conversion to dynamic programming.
-
Optimal substructure: Let’s say we want to find the solution to the problem of counting a value,
target, given numbers. Since we know the answer to the subproblems formed by subtracting each of the numbers from thetarget, we can simply sum up the answer to these subproblems. This gives us the answer to our original problem. Therefore, this problem obeys the optimal substructure property. -
Overlapping subproblems: The algorithm solves the same subproblems repeatedly, so it also has the second property of dynamic programming. For example, for
nums=[2,3,4]andtarget=6, we know that can be generated in two ways, i.e., and . Now, when we try to generate , we know that one way to generate it is using and . For this, the algorithm will try to generate again even though we’ve already computed it.
Let’s look at the dynamic programming approach to solving this problem. We first create a table, dp, of size , where is the target value. Each cell of our table, dp[i], represents the combination to make the target value
using elements from nums.
First, for target , we add “[ ]” in dp[0] because there is only one way to make a target of by using none of the available options. After this, for any target and each number in nums, we only select this number if nums[j] <= i. After selecting a number nums[j], we traverse all combinations in dp[i-nums[j]] because each combination in that cell represents a combination that can sum up to target i after adding nums[j] to it. For each such combination, we append nums[j] to it, sort it to avoid redundancy, and check whether it already exists in dp[i]. If not, we append this combination to dp[i]. We repeat this process until we’ve processed all target values. Finally, the last cell of the table, dp[target], gives us the unique combinations of nums that make up the target.
Let’s look at the following illustration to get a better understanding of the algorithm:
1 of 21
2 of 21
3 of 21
4 of 21
5 of 21
6 of 21
7 of 21
8 of 21
9 of 21
10 of 21
11 of 21
12 of 21
13 of 21
14 of 21
15 of 21
16 of 21
17 of 21
18 of 21
19 of 21
20 of 21
21 of 21
Now, let’s look at the code in the code widget below for the solution we just discussed.
Solution summary#
To recap, the solution to this problem can be divided into the following parts:
-
Initialize
dpto store the results. Each cell ofdpstores the combinations that sum up to the value, where ranges from totarget. -
Add “[ ]” in
dp[0]for target . -
For each value and number in
nums, select this number ifnums[j] <= i. -
Append
nums[j]to each previously calculated combination indp[i-nums[j]], and add it todp[i]if it doesn’t already exist in it. -
Finally, return
dp[target]that contains all the combinations that sum up totarget.
Time complexity#
The time complexity of this solution is , where is the target, is the length of nums, and , where is the minimum value in nums. This is because , , and time is taken by the first, second, and third loop, respectively. Moreover, time is taken by the sorting.
Space complexity#
The space complexity of this algorithm is .
Combination Sum
Word Break